/**
* 各种字符串算法
**/
#include <stdio.h>
#include <string.h>
#include <stdlib.h>

#define MAX_NUM  100 // 计算大数,保存结果缓存长度

/**
* 求一个字符串中连续出现次数最多的子串，请给出分析和代码
* 1个字符也是子串，注意是求连续出现次数最多的子串。
* 例如"abcbcbcabc"，中出现次数最多的是"bc"，出现3次。
* 例如"abcccabc"，中出现次数最多的是"c"，出现3次。
* 本题可以依次找出子串长度为1~len，位置从0~(len-长度)开始的子串
* 比如"abc"，可以分成a/b/c/ab/bc/abc，依次计算即可
**/
void find_sub_str(const char *str)
{
  int i, j, k, nTmp, nMax = 0, len = strlen(str) + 1;
  char *tmp = (char*)malloc(sizeof(char) * len);
  if ( NULL == tmp ) {
    exit(-1); // 申请内存失败
  }
  char *max = (char*)malloc(sizeof(char) * len);
  if ( NULL == max ) {
    exit(-1); // 申请内存失败
  }
  
  for (i = 1;i < len; ++i) {     // 每次取的子串长度
    for (j = 0;j < len-i; ++j) { // 取子串的位置
      strncpy(tmp, str+j, i); tmp[i] = '\0'; // 得到子串内容,且写字符串结尾
      
      // 从当前子串下一个i长度位置开始
      for (k = j+i, nTmp = 1; k < len-i; ) {
        if (strncmp(tmp, str+k, i) == 0) { // 比较该位置是否和子串相同
          k += i; // 找到和子串相同,则遍历下个位置
          nTmp++; // 计数子串个数
        } else {  // 首次不匹配子串,需要退出循环
          if (nTmp > 1) {
            j = k-1; // 如果连续出现多次,则从下个位置开始,由于外部循环有++,这里少加一个
          }
          break;
        }
      }
      
      if (nTmp > nMax) { // 如果当前次数大于缓存次数,则记录本次情况
        nMax = nTmp;
        strcpy(max, tmp);
      }
      //printf("%s:%d,%d,%d\n", tmp, nTmp, k, j);
    }
  }
  
  printf("%s:%d\n", max, nMax);
  free(tmp);
  free(max);
}

// 我的strstr
char *my_strstr(const char *str, const char *sub)
{
  if (str != NULL && sub != NULL) {
    int i, j;
    
    for (i = 0; str[i] != '\0'; ++i) {
      for (j = 0; sub[j] != '\0'; ++j) {
        if (str[i+j] != sub[j]) {
          break; // 匹配子串不相等,直接退出
        }
      }
      if (sub[j] == '\0') {
        return &str[i]; // 如果直接匹配到子串结尾,直接返回
      }
    }
  }
  return NULL;
}
// pdf的答案
char *pdf_strstr(const char *str, const char *sub)
{
  int i, j, tmp;
  for (i = 0;str[i] != '\0'; ++i) {
    j = 0;tmp = i;
    if (str[i] == sub[j]) {
      while (str[i++] == sub[j++]) {
        if (sub[j] == '\0') {
          return &str[i-j];
        }
      }
      i = tmp;
    }
  }
  return NULL;
}

char *convert_word(char *str)
{
  char tmpChar;
  int i, j, k, tmpi, len = strlen(str);
  char *tmpStr = (char*)malloc(sizeof(char) * (len + 1));
  if (NULL == tmpStr) {
    exit(-1); // 申请内存失败
  }
  
  for (i = 0,j = len-1; j>=0; --j, ++i) { // 本方法逆转使用中间字符串tmpStr
    tmpStr[i] = str[j]; // 翻转字符串,写入tmp
  }
  tmpStr[i] = '\0';
  printf("method 1,tmpStr:<%s>\n", tmpStr);
  
  strcpy(tmpStr, str); // 下面是本字符串逆转,不借助其他字符串
  for (k = len / 2,j = 0, i = len-1; j < k; --i,++j) { // 逆转一个单词
    tmpChar   = tmpStr[i];
    tmpStr[i] = tmpStr[j];
    tmpStr[j] = tmpChar;
  }
  printf("method 2,tmpStr:<%s>\n", tmpStr);
  
  for (i = 0,j = 0; i<len; ++i) {
    if (tmpStr[i] == ' ') { // j是单词首字母,i是字母后面空格
      tmpi = i--; // 缓存i的值,且i自减为单词尾字母
      for (k = (i + j + 1) / 2; j < k; --i,++j) { // 逆转一个单词
        tmpChar   = tmpStr[i];
        tmpStr[i] = tmpStr[j];
        tmpStr[j] = tmpChar;
      }
      i = tmpi; j = tmpi+1; // 恢复i值,且j从下个位置开始
    }
  }
  for (k = (i + j) / 2; j < k; --i,++j) { // 逆转最后一个单词
    tmpChar     = tmpStr[i-1];
    tmpStr[i-1] = tmpStr[j];
    tmpStr[j]   = tmpChar;
  }
  printf("tmpStr:<%s>\n", tmpStr);
  
  return tmpStr; // 重新分配内存避免传入常量
}
/**
* 编写一个函数,计算0 <= X <= 4 000 000 000,以内最大的那个f(n)=n的值
* 函数f的功能是统计所有0到n之间所有包含数字1的数字和。
* 比如f(13)=6
* 因为“1”在“1,2,3,4,5,6,7,8,9,10,11,12,13”中的总数是6(1,11,12,13)
**/
int count_1_my(const char *n)
{
  if (NULL == n || n[0] == '\0' || n[0] == '0') {
    return 0; // 传入为空,或者为0,直接返回
  }
  //cnt记录1的个数,end记录tmp当前最后元素位置,carry标识是否有进位
  int  cnt = 0, i, end = 0, carry;
  char tmp[16] = "1"; // 从1开始计算
  while (strcmp(tmp, n) != 0) {
    //printf("<%s>\n", tmp); // 打印当前计算哪个数字
    
    for (i = end,carry = 1; i>=0 ;--i) {
      if (tmp[i] == '1') {
        cnt++; // 统计1的个数
      }
      
      if (carry == 1) {
        tmp[i]++;       // 本位值自增1
        if (tmp[i] > '9') {
          tmp[i] = '0'; // >'9',则本位为'0'
        } else {
          carry  = 0;
        }
      } // end if
    }
    
    if (carry == 1) { // 如果最终进位为1,则字符串右移1位,最高位为'1'
      for (i = ++end; i > 0; --i) {
        tmp[i] = tmp[i-1];
      }
      tmp[0]     = '1';  // 最高位为'1'
      tmp[end+1] = '\0'; // 写字符串结束位置
    }
  }
  
  return cnt;
}

/**
* 转换字符串格式为原来字符串里的字符+该字符连续出现的个数
* 例如字符串1233422222，转化为1121324125(1出现1次,2出现1次,3出现2次,...)
* 怎么实现比较简单，
**/
char *count_num(char *str)
{
  int  i, j, cnt = strlen(str)*2 + 1; // 如果全部是单个数字,则结果要长一倍
  char tmp = str[0], *tstr = (char*)malloc(sizeof(char) * cnt); // 确保保存结果空间够用
  if (NULL == tstr) {
    exit(-1); // 内存分配失败
  }
  
  for (cnt = i = 1,j = 0; str[i-1] != '\0'; ++i) {
    if (tmp == str[i]) {
      cnt++;
    } else {
      j += sprintf(tstr+j, "%c%d", tmp, cnt); // sprintf返回结果字符串长度
      
      tmp = str[i];
      cnt = 1;
    }
  }
  tstr[j] = '\0';
  
  return tstr;
}

/* 逆置一个字符串,修改原字符串值 */
char *reverse_str1(char *str)
{
  char tmp;
  int i = 0, j = strlen(str) - 1;
  for (; i < j; ++i, --j) {
    tmp    = str[i];
    str[i] = str[j];
    str[j] = tmp;
  }
  
  return str;
}
/* 逆置一个字符串,不修改原字符串 */
char *reverse_str2(const char *str)
{
  int   i = 0, j = strlen(str) - 1;
  char *ret = (char*)malloc(sizeof(char) * (j+2)); // 申请长度len+1
  if (NULL == ret) {
    exit(-1);
  }
  
  for (; j >= 0; ++i, --j) {
    ret[i] = str[j];
  }
  ret[i] = '\0';
  
  return ret;
}

/**
* 计算正整数的+,-,*,/
* 主要是计算大数,用字符串存数,任意大的数都可以用来计算
* 没有考虑负数
**/
char *calculate_max_num(const char *a,const char *b, char opt)
{
  static char *ret = NULL; // 静态变量,ret指向的内存不必每次都申请,避免浪费
  if (NULL == ret) {       // 首次使用要申请内存
    if ( NULL == (ret = (char*)malloc(sizeof(char) * MAX_NUM)) ) {
      exit(-1); // 申请保存结果字符串,长度MAX_NUM应该够用了
    }
  }
  
  if (opt != '+' && opt != '-' && opt != '*' && opt != '/') {
    strcpy(ret, "opt not find.");
    return ret; // 操作符不是+-*/,则不必计算,直接返回
  }
  
  int i, j, k, len1, len2, carry, min, max;
  if (NULL == a || a[0] == '\0' || a[0] == '0') { // a=0
    len1 = 0;
  } else {
    len1 = strlen(a); // 得到a的长度
  }
  if (NULL == b || b[0] == '\0' || b[0] == '0') { // b=0
    len2 = 0;
  } else {
    len2 = strlen(b); // 得到b的长度
  }
  
  if (len1 == 0 && len2 == 0) { // a=0 & b=0
    ret[0] = '0'; ret[1] = '\0';
    return ret;
  }
  
  if (len1 == 0 && len2 != 0) { // a=0 & b!=0
    switch (opt) {
      case '+': // 0+b = b
        strcpy(ret, b);
      break;
      case '-': // 0-b = -b
        i = j = 0;
        ret[j++] = '-'; // 加负号
        while (i < len2) { ret[j++] = b[i++]; }
        ret[j] = '\0';
      break;
      case '*':
      case '/': // 0*b or 0/b = 0
        ret[0] = '0'; ret[1] = '\0';
      break;
    }
    return ret;
  }
  
  if (len1 != 0 && len2 == 0) { // a!=0 & b=0
    switch (opt) {
      case '+': // a+0 = a
      case '-': // a-0 = a
        strcpy(ret, a);
      break;
      case '*': // a*0 = 0
        ret[0] = '0'; ret[1] = '\0';
      break;
      case '/': // a/0
        strcpy(ret, "The dividend cannot be 0.");
      break;
    }
    return ret;
  } // 下面处理a!=0 & b!=0
  
  if (strcmp(a, b) == 0) { // 两个数相等
    ret[1] = '\0';  // 提前写结束符
    switch (opt) {
      case '-':
        ret[0] = '0';
        return ret; // 相减等于0
      break;
      
      case '/':
        ret[0] = '1';
        return ret; // 相除等于1
      break;
    }
  } // 本判断处理两个数相等的情况
  
  min = len2; max = len1; // 假设b为大数,a为小数
  char *numt, bit = '+';  // 两个保存数的指针,以及相减时的符号
  char *num1 = reverse_str2(a); // 逆置第一个数
  char *num2 = reverse_str2(b); // 逆置第二个数
  memset(ret, '\0', MAX_NUM);  // 初始全部写'\0',不用费心添加字符串结尾
  
  switch (opt) {
    case '+': // 加法
      if (len1 < len2) {
        min  = len1; max  = len2;
        numt = num1; num1 = num2; num2 = numt;
      } // 确保num1指向长数,num2指向短数
      
      for (carry = i = j = 0; i<max; ++i,++j) { // carry表示进位
        if (i < min) { // 两个数都计算
          ret[j] = num1[i]-'0' + num2[i] + carry;
        } else { // 只计算长一点的数
          ret[j] = num1[i] + carry;
        }
        
        if (ret[j] > '9') {
          ret[j] = (ret[j]-'0')%10 + '0';
          carry  = 1;
        } else {
          carry  = 0;
        }
      }
      
      if (carry == 1) { // 最终有一个进位,则最高位写1
        ret[j] = '1';
      }
    break;
    
    case '-': // 减法
      if ( len1 < len2 || ( len1 == len2 && strcmp(a, b) < 0 ) ) {
        min  = len1; max  = len2;
        numt = num1; num1 = num2; num2 = numt;
        bit  = '-'; // 结果为负数
      } // 下面的num1一定大于num2,只是结果加不加负号的区别
      
      for (carry = i = j = 0; i<max; ++i,++j) { // carry表示借位
        if (i < min) {
          ret[j] = num1[i] - num2[i] - carry + '0';
        } else {
          ret[j] = num1[i] - carry;
        }
        
        if (ret[j] < '0') {
          ret[j]+= 10;
          carry  = 1;
        } else {
          carry  = 0;
        }
      }
      
      /* 相减高位可能为0,因此需要去掉这些0 */
      while (ret[--j] == '0') {
      } // 循环结束时j为最高不为0的位
      
      if (bit == '-') { // 如果为负数,则加上符号
        ret[++j] = '-';
      }
      ret[++j]   = '\0'; // 高位0去掉
    break;
    
    case '*': // 乘法
      for (i = 0; i < len1; ++i) {
        for (k = i,carry = j = 0, bit = num1[i]-'0'; j < len2; ++j,++k) { // carry表示进位
          ret[k]   += bit * (num2[j]-'0') + carry; // 这里注意别超过char的范围
          if (ret[k] > 9) {
            carry   = ret[k]/10; // 得到进位值
            ret[k] %= 10; // 得到本位值
          } else {
            carry   = 0; // 进位值清零
          }
        }
        
        if (carry > 0) { // 最终有进位,则写入
          ret[k] = carry;
        }
      }
      
      if (carry > 0) { // 最终有进位,则写入
        ret[k++] = carry;
      }
      
      for (i = 0;i < k;++i) {
        ret[i] += '0'; // 将数字转换为字符
      }
    break;
    
    case '/': // 除法
      
    break;
  }
  free(num1); free(num2); // 释放临时申请存放字符串的内存
  
  return reverse_str1(ret); // 结果要逆置
}

/* 判断数字是否为回文数,返回0则不是,返回1则是 */
int palindromic_number(int n)
{
  char str[16];
  int  i = 0, j = sprintf(str, "%d", n) - 1;
  for (; i < j; ++i,--j) {
    if (str[i] != str[j]) {
      return 0;
    }
  }
  return 1;
}

int main(int argc, char *argv[])
{
  int i;
  char str[MAX_NUM] = "abcbcbcabc";
  find_sub_str(str);
  
  char *p = my_strstr("12345678", "345");
  printf("my:%s\n", p);
  p = pdf_strstr("12345678", "345");
  printf("pdf:%s\n", p);
  
  convert_word("i'm come from tianjin.");
  
  printf("count_1_my:%d\n", count_1_my("400"));
  
  strcpy(str, "1233333333333333333499999999999299999988957766");
  printf("count_num:%s\n", count_num(str));
  
  strcpy(str, "12346789");
  printf("reverse_str1:%s\n", reverse_str1(str));
  
  /** 输出回文数
  for (i=0;i<10000;i++) {
    if (palindromic_number(i) == 1) {
      printf("palindromic number:%d\n", i);
    }
  }
  */
  
  printf("<%s>\n", calculate_max_num("23423", "12312", '+'));
  printf("<%s>\n", calculate_max_num("0", "1256456453", '-'));
  printf("<%s>\n", calculate_max_num("123", "0", '*'));
  printf("<%s>\n", calculate_max_num("32423", "0", '/'));
  
  return 0;
}
